package link_list

// https://leetcode.cn/problems/reverse-linked-list/ leetcode-206

// 递归
func reverseList0(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	newHead := reverseList0(head.Next)
	head.Next.Next = head
	// 如果没有这一行，最后会形成最后两个节点的双向链表，永远无法结束，例如 5->4->3->2->1->2
	head.Next = nil
	return newHead
}

// 迭代
func reverseList1(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var newHead *ListNode
	for head != nil {
		tmp := head.Next
		head.Next = newHead
		newHead = head
		head = tmp
	}
	return newHead
}
